// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ssa

import (
	"math/big"
	"math/bits"
)

// 所以你想计算一些常数c的x/c？
// 机器除法指令很慢，所以我们尝试用乘法+几个
// 来计算这个除法，而不是其他便宜的指令。
// （我们在这里假设c！=0、+/-1或+/-2^i。这些
// 案例很容易以不同的方式处理）。

// 来自https:

// 1/c小于1，所以我们不能在
// 整数算法中直接计算它。让我们计算2^e/c 
// 的值e TBD（^=指数）。然后
// ⎣x/c⎦ = ⎣x*（2^e/c）/2^e⎦. 
// 除以2^e很容易。不幸的是，e/c不是整数。
// 所以我们必须近似计算。我们把它的近似值称为m.
// 然后我们将计算
// ⎣x*m/2^e⎦ 
// 我们希望与之平等⎣x/c⎦ 对于0<=x<2^n-1 
// 其中n是单词大小。
// 设置x=c将得到c*m>=2^e。
// 我们将选择m=⎡2^e/c⎤ 满足这个等式。
// 剩下的就是选择e.
// 让m=2^e/c+delta，0<=delta<1 
// ⎣x*（2^e/c+delta）/2^e⎦ 
// ⎣x/c+x*增量/2^e⎦ 
// 我们必须有x*delta/2^e<1/c，这样这个
// 附加项的循环方式就不会与⎣x/c⎦ 做
// 重新排列，
// 2^e>x*delta*c 
// x最多可以是2^n-1，delta最多可以是1。
// 所以2^e>=2^n*c就足够了。
// 所以我们选择e=n+s，其中s=⎡log2（c）⎤. 
// 
// 由于m中有n+1位，因此会产生额外的复杂性。
// 硬件将我们限制为n位乘以n位。
// 我们分为三种情况：
// 
// 情况1:m是偶数。
// ⎣x/c⎦ = ⎣x*m/2^（n+s）⎦ 
// ⎣x/c⎦ = ⎣x*（m/2）/2^（n+s-1）⎦ 
// ⎣x/c⎦ = ⎣x*（m/2）/2^n/2^（s-1）⎦ 
// ⎣x/c⎦ = ⎣⎣x*（m/2）/2^n⎦ / 2^（s-1）⎦ 
// 乘法+移位
// 
// 情况2:c是偶数。
// ⎣x/c⎦ = ⎣（x/2）/（c/2）⎦ 
// ⎣x/c⎦ = ⎣⎣x/2⎦ / （c/2）⎦ 
// 这只是最初的问题，x'=⎣x/2⎦, c'=c/2，n'=n-1。
// s'=s-1 
// m'=⎡2^（n'+s'）/c'⎤ 
// /=⎡2^（n+s-1）/c⎤ 
// /=⎡m/2⎤ 
// ⎣x/c⎦ = ⎣x'*m'/2^（n'+s'）⎦ 
// ⎣x/c⎦ = ⎣⎣x/2⎦ * ⎡m/2⎤ / 2^（n+s-2）⎦ 
// ⎣x/c⎦ = ⎣⎣⎣x/2⎦ * ⎡m/2⎤ / 2^n⎦ / 2^（s-2）⎦ 
// 移位+乘法+移位
// 
// 情况3：其他所有
// 让k=m-2^n。k适合n位。
// ⎣x/c⎦ = ⎣x*m/2^（n+s）⎦ 
// ⎣x/c⎦ = ⎣x*（2^n+k）/2^（n+s）⎦ 
// ⎣x/c⎦ = ⎣（x+x*k/2^n）/2^s⎦ 
// ⎣x/c⎦ = ⎣（x+⎣x*k/2^n⎦) / 2^s⎦ 
// ⎣x/c⎦ = ⎣（x+⎣x*k/2^n⎦) / 2^s⎦ 
// ⎣x/c⎦ = ⎣⎣（x+⎣x*k/2^n⎦) / 2.⎦ / 2^（s-1）⎦ 
// 乘法+avg+shift 
// 
// 这些可以在硬件中使用实现：
// ⎣a*b/2^n⎦ - n位乘n位乘法的高n位。
// ⎣（a+b）/2⎦   - 也就是两个n位数字的“平均值”。
// （不只是常规的加法和移位，因为中间结果
// a+b中有n+1位。不过，可以在x86上的2条指令中完成
// 。）

// umagicOK报告我们是否应该将n位除以c。
func umagicOK(n uint, c int64) bool {
	// 将常量生长素值转换为它们所代表的实际uint64常数。
	d := uint64(c) << (64 - n) >> (64 - n)

	// 不适用于0。
	// 不要使用2的幂。
	return d&(d-1) != 0
}

// umagicockn报告我们是否应该将一个无符号的n位除以c进行强度缩减。
// 当c！=0和c不是二的幂。
func umagicOK8(c int8) bool   { return c&(c-1) != 0 }
func umagicOK16(c int16) bool { return c&(c-1) != 0 }
func umagicOK32(c int32) bool { return c&(c-1) != 0 }
func umagicOK64(c int64) bool { return c&(c-1) != 0 }

type umagicData struct {
	s int64  // ⎡log2（c）⎤ 
	m uint64 // ⎡2^（n+s）/c⎤ - 2^n 
}

// umagic计算将无符号n位除以常数uint64（c）所需的常数。
// 返回值满足所有0<=x<2^n 
// floor（x/uint64（c））=x*（m+2^n）>>（n+s）
func umagic(n uint, c int64) umagicData {
	// 将ConstX auxint值转换为它们所代表的实际uint64常数。
	d := uint64(c) << (64 - n) >> (64 - n)

	C := new(big.Int).SetUint64(d)
	s := C.BitLen()
	M := big.NewInt(1)
	M.Lsh(M, n+uint(s))     // 2^（n+s）
	M.Add(M, C)             // 2^（n+s）+c 
	M.Sub(M, big.NewInt(1)) // 2^（n+s）+c-1 
	M.Div(M, C)             // ⎡2^（n+s）/c⎤ 
	if M.Bit(int(n)) != 1 {
		panic("n+1st bit isn't set")
	}
	M.SetBit(M, int(n), 0)
	m := M.Uint64()
	return umagicData{s: int64(s), m: m}
}

func umagic8(c int8) umagicData   { return umagic(8, int64(c)) }
func umagic16(c int16) umagicData { return umagic(16, int64(c)) }
func umagic32(c int32) umagicData { return umagic(32, int64(c)) }
func umagic64(c int64) umagicData { return umagic(64, c) }

// 对于签约部门，我们使用类似的策略。
// 首先，我们强制执行一个正c。
// x/c=-（x/（-c））
// 这将要求c<0的额外负op。
// 
// 如果x为正，我们的状态与上面未签名的情况非常相似。我们定义：
// s=⎡log2（c）⎤-1 
// m=⎡2^（n+s）/c⎤ 
// 然后
// ⎣x/c⎦ = ⎣x*m/2^（n+s）⎦ 
// 如果x为负，我们有
// ⎡x/c⎤ = ⎣x*m/2^（n+s）⎦ + 1 
// /（TODO:派生？）
// 
// 乘法有点奇怪，因为它是有符号n位值
// 乘以无符号n位值。对于小于
// 字长的n，我们可以适当扩展x和m，并使用
// 有符号乘法指令。对于n==字长，
// 我们必须使用带符号的乘法高位，并通过加x*2^n来更正
// 结果。
// 
// 如果x<0是通过减去x>>来加1（n-1）。

func smagicOK(n uint, c int64) bool {
	if c < 0 {
		// 不适用于负c。
		return false
	}
	// 不适用于0。
	// 不要将其用于2的幂。
	return c&(c-1) != 0
}

// smagicockn报告我们是否应该将有符号的n位除以c。
func smagicOK8(c int8) bool   { return smagicOK(8, int64(c)) }
func smagicOK16(c int16) bool { return smagicOK(16, int64(c)) }
func smagicOK32(c int32) bool { return smagicOK(32, int64(c)) }
func smagicOK64(c int64) bool { return smagicOK(64, c) }

type smagicData struct {
	s int64  // ⎡log2（c）⎤-1 
	m uint64 // ⎡2^（n+s）/c⎤ 
}

// magic计算将有符号n位除以常数c所需的常数。
// 必须具有c>0。返回值满足所有-2^（n-1）<=x<2^（n-1）
// /trunc（x/c）=x*m>（n+s）+（x<0？1:0）
func smagic(n uint, c int64) smagicData {
	C := new(big.Int).SetInt64(c)
	s := C.BitLen() - 1
	M := big.NewInt(1)
	M.Lsh(M, n+uint(s))     // /2^（n+s）
	if M.Bit(int(n)) != 0 {
		panic("n+1st bit is set")
	}
	if M.Bit(int(n-1)) == 0 {
		panic("nth bit is not set")
	}
	m := M.Uint64()
	return smagicData{s: int64(s), m: m}
}

func smagic8(c int8) smagicData   { return smagic(8, int64(c)) }
func smagic16(c int16) smagicData { return smagic(16, int64(c)) }
func smagic32(c int32) smagicData { return smagic(32, int64(c)) }
func smagic64(c int64) smagicData { return smagic(64, c) }

// 与直接计算
// 模x%c并与0进行比较相比，可以更有效地检查整除性x%c==0。
// 
// Granlund和Montgomery在上面提到的同一篇论文
// 中简要地提到了这种方法
// 沃伦在《黑客之乐》第10-17节
// 
// 首先要注意的是，对于奇数整数，精确除法可以通过使用与字长2^n有关的模逆来计算。如果给定c，计算m，使得（c*m）mod 2^n==1 
// 那么如果c除以x（x%c==0），商由q=x/c==x*m mod 2^n 
// 
// 因此，x*m mod 2^n为0,1,2,3。。。⎣（2^n-1）/c⎦ 
// 即商取从零到最大的所有值=⎣（2^n-1）/c⎦ 
// 
// 如果x不能被c整除，那么x*m mod 2^n必须取大于最大值的值。
// 
// 这就给出了x*m mod 2^n<=⎣（2^n-1）/c⎦ 作为可分性测试
// 涉及一次乘法和比较。ABCFDG 
// 我们可以测试x是否可以被d0和2^k整除。
// 对于d0，测试与上面相同。设m为m*d0 mod 2^n==1 
// 然后x*m mod 2^n<=⎣（2^n-1）/d0⎦ 这是第一次测试。
// 被2^k整除的测试是对k个尾随零的检查。
// 注意，由于d0是奇数，m是奇数，因此x*m将有与x相同数量的
// 尾随零。因此这两个测试是，
// 
// x*m mod 2^n<=⎣（2^n-1）/d0⎦ 
// 和x*m以k个零位结尾
// 
// 这些可以通过以下
// （黑客喜欢的定理ZRU）组合成一个单一的无符号整数比较。
// 
// x<=a和x以k个零位结尾当且仅当RotRight（x，k）<=⎣a/（2^k）⎦ 
// 其中RotRight（x，k）是x乘以k位的右旋转。
// 
// 证明第一个方向，x<=a->⎣x/（2^k）⎦ <= ⎣a/（2^k）⎦ 
// 但是由于x以k结尾，所有旋转的位也都是零。
// So rottright（x，k）=⎣x/（2^k）⎦ <= ⎣a/（2^k）⎦ 
// 
// 如果x不以k个零位结尾，则RotRight（x，k）
// 在k个最高位中有一些非零位。
// ⎣x/（2^k）⎦ 在k个最高位中都有零，
// so rottright（x，k）>⎣x/（2^k）⎦ 
// 
// 最后，如果x>a且有k个尾随零位，则RotRight（x，k）=⎣x/（2^k）⎦ 
// 和⎣x/（2^k）⎦ 必须大于⎣a/（2^k）⎦, 也就是说，x的前n-k位必须
// 大于a的前n-k位，因为其余的x位为零。
// 
// 因此，关于的两个条件可以替换为单个测试
// 
// RotRight（x*m mod 2^n，k）<=⎣（2^n-1）/c⎦ 
// 
// 其中d0*2^k在右侧被c替换。

// udivisibleOK报告我们是否应该通过c来减少无符号n位除数检查。
func udivisibleOK(n uint, c int64) bool {
	// 将常量生长素值转换为它们所代表的实际uint64常量。
	d := uint64(c) << (64 - n) >> (64 - n)

	// 不适用于0。
	// 不要使用2的幂。
	return d&(d-1) != 0
}

func udivisibleOK8(c int8) bool   { return udivisibleOK(8, int64(c)) }
func udivisibleOK16(c int16) bool { return udivisibleOK(16, int64(c)) }
func udivisibleOK32(c int32) bool { return udivisibleOK(32, int64(c)) }
func udivisibleOK64(c int64) bool { return udivisibleOK(64, c) }

type udivisibleData struct {
	k   int64  // trailingZeros（c）
	m   uint64 // m*（c>>k）mod 2^n==1奇数部分模2^n的乘法逆
	max uint64 // ⎣（2^n-1）/c⎦ 整除性最大值
}

func udivisible(n uint, c int64) udivisibleData {
	// 将常量生长素值转换为它们所代表的实际uint64常量。
	d := uint64(c) << (64 - n) >> (64 - n)

	k := bits.TrailingZeros64(d)
	d0 := d >> uint(k) // 除数的奇数部分

	mask := ^uint64(0) >> (64 - n)

	// 用牛顿法计算乘法逆。
	// 二次收敛使每次迭代的正确位数加倍。
	m := d0            // 初始猜测更正为3位d0*d0 mod 8==1 
	m = m * (2 - m*d0) // 6位
	m = m * (2 - m*d0) // 12位
	m = m * (2 - m*d0) // 24位
	m = m * (2 - m*d0) // 48位
	m = m * (2 - m*d0) // 96位>=64位
	m = m & mask

	max := mask / d

	return udivisibleData{
		k:   int64(k),
		m:   m,
		max: max,
	}
}

func udivisible8(c int8) udivisibleData   { return udivisible(8, int64(c)) }
func udivisible16(c int16) udivisibleData { return udivisible(16, int64(c)) }
func udivisible32(c int32) udivisibleData { return udivisible(32, int64(c)) }
func udivisible64(c int64) udivisibleData { return udivisible(64, c) }

// 对于带符号整数，类似的方法如下。
// 
// 给定c>1且奇数，计算m，使（c*m）mod 2^n==1 
// 如果c除以x（x%c==0），商由q=x/c==x*m mod 2^n 
// 
// x的范围为⎡-2^（n-1）/c⎤ * c、 -c、 0，c。。。⎣（2^（n-1）-1）/c⎦ * c 
// 因此，x*m mod 2^n是⎡-2^（n-1）/c⎤, ... -2, -1, 0, 1, 2, ... ⎣（2^（n-1）-1）/c⎦ 
// 
// 所以，x是c的倍数当且仅当：
// ⎡-2^（n-1）/c⎤ <= x*m模块2^n<=⎣(二)(一)⎦ 
// 
// 由于c>1且为奇数，因此可以通过
// ⎡-2^（n-1）/c⎤ == ⎡（-2^（n-1）+1）/c⎤ == -⎣（2^（n-1）-1）/c⎦ 
// 
// -⎣（2^（n-1）-1）/c⎦ <= x*m模块2^n<=⎣（2^（n-1）-1）/c⎦ ABCFDG 
// 
// 要将其转换为一个比较，我们使用以下定理（黑客喜欢ZRS）。
// 
// 对于a>=0，以下条件是等效的：
// 1）-a<=x<=a，x以至少k 0位结束
// 2）旋转权（x+a'，k）<=⎣2a'/2^k⎦ 
// 
// 其中a'=a&-2^k（a的右k位设置为零）
// 
// 要看到1和2是等价的，请注意-a<=x<=a相当于
// /-a'<=x<=a'，如果且仅当x以至少k 0位结尾。每边加上-a，表示
// 0<=x+a'<=2a'和x+a'至少以k0位结束，当且仅当x结束，因为a'定义为
// k0位。我们可以使用上面的定理ZRU，其中x->x+a'和a->2a'给出1）==2）。
// 
// 设m为（d0*m）mod 2^n==1。
// 设q=x*m模2^n.
// 设a'=⎣（2^（n-1）-1）/d0⎦ & -2^k 
// 
// 那么可除性测试是：
// 
// RotRight（q+a'，k）<=⎣2a'/2^k⎦ 
// 
// 请注意，计算是使用无符号整数执行的。
// 由于a'可以有n-1位，2a'可能有n位，因此没有溢出的风险。

// sdivisibleOK报告我们是否应该通过c减少签名的n位除数检查。
func sdivisibleOK(n uint, c int64) bool {
	if c < 0 {
		// 不适用于负c。
		return false
	}
	// 不适用于0。
	// 不要将其用于2的幂。
	return c&(c-1) != 0
}

func sdivisibleOK8(c int8) bool   { return sdivisibleOK(8, int64(c)) }
func sdivisibleOK16(c int16) bool { return sdivisibleOK(16, int64(c)) }
func sdivisibleOK32(c int32) bool { return sdivisibleOK(32, int64(c)) }
func sdivisibleOK64(c int64) bool { return sdivisibleOK(64, c) }

type sdivisibleData struct {
	k   int64  // trailingZeros（c）
	m   uint64 // m*（c>>k）mod 2^n==1奇数部分模2^n的乘法逆
	a   uint64 // ⎣（2^（n-1）-1）/（c>>k）⎦ & -（1<<k）加性常数
	max uint64 // /⎣（2 a）/（1<<k）⎦ 除数
}

func sdivisible(n uint, c int64) sdivisibleData {
	d := uint64(c)
	k := bits.TrailingZeros64(d)
	d0 := d >> uint(k) // 除数

	mask := ^uint64(0) >> (64 - n)

	// 的奇数部分通过牛顿法计算乘法逆。
	// 二次收敛使每次迭代的正确位数加倍。
	m := d0            // 初始猜测正确到3位d0*d0 mod 8==1 
	m = m * (2 - m*d0) // 6位
	m = m * (2 - m*d0) // 12位
	m = m * (2 - m*d0) // 24位
	m = m * (2 - m*d0) // 48位
	m = m * (2 - m*d0) // 96位>=64位
	m = m & mask

	a := ((mask >> 1) / d0) & -(1 << uint(k))
	max := (2 * a) >> uint(k)

	return sdivisibleData{
		k:   int64(k),
		m:   m,
		a:   a,
		max: max,
	}
}

func sdivisible8(c int8) sdivisibleData   { return sdivisible(8, int64(c)) }
func sdivisible16(c int16) sdivisibleData { return sdivisible(16, int64(c)) }
func sdivisible32(c int32) sdivisibleData { return sdivisible(32, int64(c)) }
func sdivisible64(c int64) sdivisibleData { return sdivisible(64, c) }
